LFSRs are well known in the art. Typically, these devices are utilized in operations where the generation of a pseudonoise/pseudorandom (PN) code sequence is required A PN code sequence is a binary signal which appears to be random. In reality, a PN code sequence is not random at all; it is a deterministic, periodic signal whose periodicity is dependent upon the number of stages within the LFSR, the feedback taps, and the LFSR's initial conditions. Typical operations employing LFSR's as PN code sequence generators are: spread spectrum systems, noise generators, and cryptographic systems.
FIG. 1 depicts a simplistic representation of an LFSR 100. Mathematically, the LFSR defines an Nth degree polynomial (where N is the length of the LFSR) with one coefficient for each "tap" (output bit) used to form the feedback signal Accordingly, the LFSR 100 is definable as a fourth degree polynomial, comprising the four stages 11-14, with feedback signal .sup.T 1, obtained from the exclusive-or gate 15 acting upon the output of stages 13 and 14. .sup.T 1 is then fed back to the input of stage 11. It will be appreciated by those skilled in the art that the LFSR 100 is a simplistic model of a PN code sequence generator, selected primarily to show that an LFSR of the Nth degree is ultimately periodic in 2.sup.n -1 bits (see Table 1).
It will also be appreciated that the LFSR 100 represents a TYPE I LFSR. Type I, as used herein, defines an LFSR wherein the various flip flops or stages are cascaded together, input to output, without interruption by an intervening feedback signal. This configuration, which is typically based upon a hardware model, facilitates a simple determination of the LFSR's state. Accordingly, the four bits of information found in stages 11-14 of the LFSR 100 are readily available.
This noted characteristic of the TYPE I LFSR, represents a decided advantage over alternative LFSR implementations which provide an identical output sequence. In many instances, the ability to simply replicate a TYPE I LFSR PN sequence is insufficient. Often, it is extremely important to know the state of a specific TYPE I LFSR stage, in conjunction with the PN output sequence. This data is often used in the performance of error-correction routines, phase continuity detection checks, and other control functions vital to overall system operation. TYPE I LFSRs enjoy this capability and therefore are still heavily used in computers and digital processing systems.
Referring now to FIG. 2, FIG.2 depicts the LFSR 100 of FIG. 1 in its alternative configuration. The LFSR 200 of FIG. 2 is a TYPE II LFSR. TYPE II, as used herein, defines an LFSR wherein the various stages are cascaded together, however, the shift path is interrupted by the introduction of a feedback signal.
The LFSR 200 consists of four stages 21-24, an exclusive-or gate 25, and a feedback signal .sup.T 2. According to this implementation, the exclusive-or gate 25 performs an exclusive-or operation on the outputs of stage 24 and 21. This operation is then used to determine the state of stage 22. Finally, the output of 24 is fed back to the input of stage 21. Of importance, Table 2, which denotes the operation of the LFSR 200, confirms that the output sequences generated by the TYPE I LFSR 100 and the TYPE II LFSR 200 are identical, but for the phase discontinuity caused by a timing shift. This output sequence appears as the pattern of bits in the 4th stages of LFSR 100 and 200. This same pattern of bits is repeated in each other stage, once again shifted in time.
TYPE II LFSR's are generally based upon software models, and are therefore extremely economical, and efficient to implement in modern computers and digital processors This becomes increasingly true as the number of stages and feedback taps increase. For instance, FIG. 1 and FIG. 2 both depict simplistic examples of LFSR's employing only four stages and a single tap. In practice, however, a moderate PN code sequence generator will employ in excess of 30 stages with anywhere from 1 to 30 feedback taps In the preferred embodiment, LFSR 200 comprises a 64 stage shift register, providing a 64th degree polynomial. Approximately 32 taps are used to create the desired PN code sequence. This 64 bit maximal length LFSR will produce a sequence having approximately 1.84.times.10.sup.19 bits. At 12 KHz, it will take nearly 48.7.times.10.sup.6 years for this sequence to repeat.
As PN code sequence generators continue to increase in sophistication, the modern trend is to employ the software implemented TYPE II LFSR where feasible. Unfortunately, the easier to implement TYPE II LFSR does not facilitate an easy or direct determination of the internal state of a TYPE I LFSR. While it is possible to compute the state of a TYPE I, the complexity of this operation and the impact upon system processing power mitigates the benefit derived from utilizing a TYPE II LFSR. Consequently, the inability of a TYPE II LFSR to directly determine the internal state of a corresponding TYPE I LFSR represents a major drawback in the design of a PN code sequence generator utilizing TYPE II LFSRs. This is particularly true in systems designed around a TYPE I implementation.
In order to remove this barrier, it would be extremely advantageous to provide a method of simulating the state of a TYPE I LFSR from information available as a result of a TYPE II LFSR implementation.